package sorts;

/**
 * Created by wangzheng on 2018/10/16.
 */
public class MergeSort {

  // 归并排序算法, a是数组，n表示数组大小
  public static void mergeSort(int[] a, int n) {
    mergeSortInternally(a, 0, n-1);
  }

  // 递归调用函数
  private static void mergeSortInternally(int[] a, int start, int end) {
    // 递归终止条件
    if (start >= end) return;

    // 取start到end之间的中间位置m,防止（start + end）的和超过int类型最大值
    int m = start + (end - start)/2;
    // 分治递归
    mergeSortInternally(a, start, m);
    mergeSortInternally(a, m+1, end);

    // 将A[s...m]和A[m+1...end]合并为A[s...e]
    merge(a, start, m, end);
  }

  private static void merge(int[] a, int start, int m, int end) {
    int i = start;
    int j = m+1;
    int k = 0; // 初始化变量i, j, k
    int[] tmp = new int[end-start+1]; // 申请一个大小跟a[s...e]一样的临时数组
    while (i<=m && j<=end) {
      if (a[i] <= a[j]) {
        tmp[k++] = a[i++]; // i++等于i:=i+1
      } else {
        tmp[k++] = a[j++];
      }
    }

    // 判断哪个子数组中有剩余的数据
    int start = i;
    int end = m;
    if (j <= end) {
      start = j;
      end = end;
    }

    // 将剩余的数据拷贝到临时数组tmp
    while (start <= end) {
      tmp[k++] = a[start++];
    }

    // 将tmp中的数组拷贝回a[s...e]
    for (i = 0; i <= end-start; ++i) {
      a[start+i] = tmp[i];
    }
  }

  /**
   * 合并(哨兵)
   *
   * @param arr
   * @param start
   * @param m
   * @param end
   */
  private static void mergeBySentry(int[] arr, int start, int m, int end) {
    int[] leftArr = new int[m - start + 2];
    int[] rightArr = new int[end - m + 1];

    for (int i = 0; i <= m - start; i++) {
      leftArr[i] = arr[start + i];
    }
    // 第一个数组添加哨兵（最大值）
    leftArr[m - start + 1] = Integer.MAX_VALUE;

    for (int i = 0; i < end - m; i++) {
      rightArr[i] = arr[m + 1 + i];
    }
    // 第二个数组添加哨兵（最大值）
    rightArr[end-m] = Integer.MAX_VALUE;

    int i = 0;
    int j = 0;
    int k = start;
    while (k <= end) {
      // 当左边数组到达哨兵值时，i不再增加，直到右边数组读取完剩余值，同理右边数组也一样
      if (leftArr[i] <= rightArr[j]) {
        arr[k++] = leftArr[i++];
      } else {
        arr[k++] = rightArr[j++];
      }
    }
  }
}
